{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check If String Is Transformable With Substring Sort Operations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: isTransformable"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #检查字符串是否可以通过排序子字符串得到另一个字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个字符串&nbsp;<code>s</code> 和&nbsp;<code>t</code>&nbsp;，请你通过若干次以下操作将字符串&nbsp;<code>s</code>&nbsp;转化成字符串&nbsp;<code>t</code>&nbsp;：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选择 <code>s</code>&nbsp;中一个 <strong>非空</strong>&nbsp;子字符串并将它包含的字符就地 <strong>升序</strong>&nbsp;排序。</li>\n",
    "</ul>\n",
    "\n",
    "<p>比方说，对下划线所示的子字符串进行操作可以由&nbsp;<code>&quot;1<strong>4234</strong>&quot;</code>&nbsp;得到&nbsp;<code>&quot;1<strong>2344</strong>&quot;</code>&nbsp;。</p>\n",
    "\n",
    "<p>如果可以将字符串 <code>s</code>&nbsp;变成 <code>t</code>&nbsp;，返回 <code>true</code>&nbsp;。否则，返回 <code>false</code>&nbsp;。</p>\n",
    "\n",
    "<p>一个 <strong>子字符串</strong>&nbsp;定义为一个字符串中连续的若干字符。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;84532&quot;, t = &quot;34852&quot;\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>你可以按以下操作将 s 转变为 t ：\n",
    "&quot;84<strong>53</strong>2&quot; （从下标 2 到下标 3）-&gt; &quot;84<strong>35</strong>2&quot;\n",
    "&quot;<strong>843</strong>52&quot; （从下标 0 到下标 2） -&gt; &quot;<strong>348</strong>52&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;34521&quot;, t = &quot;23415&quot;\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>你可以按以下操作将 s 转变为 t ：\n",
    "&quot;<strong>3452</strong>1&quot; -&gt; &quot;<strong>2345</strong>1&quot;\n",
    "&quot;234<strong>51</strong>&quot; -&gt; &quot;234<strong>15</strong>&quot;\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;12345&quot;, t = &quot;12435&quot;\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = &quot;1&quot;, t = &quot;2&quot;\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>s.length == t.length</code></li>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 和&nbsp;<code>t</code>&nbsp;都只包含数字字符，即&nbsp;<code>&#39;0&#39;</code>&nbsp;到&nbsp;<code>&#39;9&#39;</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-if-string-is-transformable-with-substring-sort-operations](https://leetcode.cn/problems/check-if-string-is-transformable-with-substring-sort-operations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-if-string-is-transformable-with-substring-sort-operations](https://leetcode.cn/problems/check-if-string-is-transformable-with-substring-sort-operations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"84532\"\\n\"34852\"', '\"34521\"\\n\"23415\"', '\"12345\"\\n\"12435\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        n = len(s)\n",
    "        pos = {i: collections.deque() for i in range(10)}\n",
    "        for i, digit in enumerate(s):\n",
    "            pos[int(digit)].append(i)\n",
    "        \n",
    "        for i, digit in enumerate(t):\n",
    "            d = int(digit)\n",
    "            if not pos[d]:\n",
    "                return False\n",
    "            if any(pos[j] and pos[j][0] < pos[d][0] for j in range(d)):\n",
    "                return False\n",
    "            pos[d].popleft()\n",
    "        \n",
    "        return True\n",
    "\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        n = len(s)\n",
    "        pos = {i : deque() for i in range(10)}\n",
    "        for i , d in enumerate(s):\n",
    "            pos[int(d)].append(i)\n",
    "        \n",
    "        for i , digit in enumerate(t):\n",
    "            d = int(digit)\n",
    "            if not pos[d]:\n",
    "                return False\n",
    "            if any(pos[j] and pos[j][0] < pos[d][0] for j in range(d)):\n",
    "                return False\n",
    "            pos[d].popleft()\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # 冒泡排序\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        n = len(s)\n",
    "        pos = {i: collections.deque() for i in range(10)}\n",
    "        for i, digit in enumerate(s):\n",
    "            pos[int(digit)].append(i)\n",
    "        \n",
    "        for i, digit in enumerate(t):\n",
    "            d = int(digit)\n",
    "            if not pos[d]:\n",
    "                return False\n",
    "            if any(pos[j] and pos[j][0] < pos[d][0] for j in range(d)):\n",
    "                return False\n",
    "            pos[d].popleft()\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        n = len(s)\n",
    "        pos = {i: deque() for i in range(10)}\n",
    "        for i, digit in enumerate(s):\n",
    "            pos[int(digit)].append(i)\n",
    "\n",
    "        for i, digit in enumerate(t):\n",
    "            d = int(digit)\n",
    "            if not pos[d]:\n",
    "                return False\n",
    "            for j in range(d):\n",
    "                if pos[j] and pos[j][0] < pos[d][0]:\n",
    "                    return False\n",
    "            pos[d].popleft()\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "  def isTransformable(self, s: str, t: str) -> bool:\n",
    "    idx = defaultdict(deque)\n",
    "    for i, c in enumerate(s):\n",
    "      idx[int(c)].append(i)\n",
    "    for c in t:\n",
    "      d = int(c)\n",
    "      if not idx[d]: return False\n",
    "      for i in range(d):\n",
    "        if idx[i] and idx[i][0] < idx[d][0]: return False\n",
    "      idx[d].popleft()\n",
    "    return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        n = len(s)\n",
    "        pos = {i: collections.deque() for i in range(10)}\n",
    "        for i, digit in enumerate(s):\n",
    "            pos[int(digit)].append(i)\n",
    "        \n",
    "        for i, digit in enumerate(t):\n",
    "            d = int(digit)\n",
    "            if not pos[d]:\n",
    "                return False\n",
    "            if any(pos[j] and pos[j][0] < pos[d][0] for j in range(d)):\n",
    "                return False\n",
    "            pos[d].popleft()\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        sn = len(s)\n",
    "        tn = len(t)\n",
    "        if sn != tn:\n",
    "            return False\n",
    "        \n",
    "        digit_idxs = [collections.deque() for _ in range(10)]\n",
    "        for i, c in enumerate(s):\n",
    "            digit_idxs[int(c)].append(i)\n",
    "        \n",
    "        for c in t:\n",
    "            d = int(c)\n",
    "            if len(digit_idxs[d]) == 0:     #s中没有d了。提供不出来了\n",
    "                return False\n",
    "            for x in range(d):              #s中，比d小的数字，不能出现在d的左侧\n",
    "                if digit_idxs[x] and digit_idxs[x][0] < digit_idxs[d][0]:\n",
    "                    return False\n",
    "            digit_idxs[d].popleft()\n",
    "\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        d = defaultdict(deque)\n",
    "        for i, j in enumerate(s):\n",
    "            d[j].append(i)\n",
    "        for i in t:\n",
    "            if not d[i]:\n",
    "                return False\n",
    "            for j in range(0, int(i)):\n",
    "                if d[str(j)] and d[str(j)][0] < d[i][0]:\n",
    "                    return False \n",
    "            d[i].popleft()\n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        mp = [deque() for _ in range(10)]\n",
    "        for i, ch in enumerate(s):\n",
    "            mp[int(ch)].append(i)\n",
    "        for ch in t:\n",
    "            ch = int(ch)\n",
    "            v = mp[ch]\n",
    "            if len(v) == 0:\n",
    "                return False\n",
    "            for less in range(ch):\n",
    "                if len(mp[less]) > 0 and mp[less][0] < v[0]:\n",
    "                    return False\n",
    "            mp[ch].popleft()\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        if len(s) != len(t): return False\n",
    "        n = len(s)\n",
    "        pos = [deque() for _ in range(10)]\n",
    "        for i, c in enumerate(s):\n",
    "            pos[int(c)].append(i)\n",
    "        for j in range(n):\n",
    "            num = int(t[j])\n",
    "            if len(pos[num]) == 0: return False\n",
    "\n",
    "            for i in range(num):\n",
    "                if len(pos[i]) != 0 and pos[i][0] < pos[num][0]: return False\n",
    "            pos[num].popleft()\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        test = [deque() for _ in range(10)]\n",
    "        for i, c in enumerate(s):\n",
    "            test[int(c)].append(i)\n",
    "        for c in t:\n",
    "            if not test[int(c)]:\n",
    "                return False\n",
    "            for i in range(int(c)):\n",
    "                if test[i] and test[i][0] < test[int(c)][0]:\n",
    "                    return False\n",
    "            test[int(c)].popleft()\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        n = len(s)\n",
    "        pos = {i: collections.deque() for i in range(10)}\n",
    "        for i, digit in enumerate(s):\n",
    "            pos[int(digit)].append(i)\n",
    "        \n",
    "        for i, digit in enumerate(t):\n",
    "            d = int(digit)\n",
    "            if not pos[d]:\n",
    "                return False\n",
    "            if any(pos[j] and pos[j][0] < pos[d][0] for j in range(d)):\n",
    "                return False\n",
    "            pos[d].popleft()\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        n = len(s)\n",
    "        pos = defaultdict(lambda : deque())\n",
    "        for i, c in enumerate(s):\n",
    "            pos[int(c)].append(i)\n",
    "        for i, c in enumerate(t):\n",
    "            d = int(c)\n",
    "            # 将这个数字移动到i位置\n",
    "            if not pos[d]:\n",
    "                return False\n",
    "            if any(pos[j] and pos[j][0] < pos[d][0] for j in range(d)):\n",
    "                return False\n",
    "            pos[d].popleft()\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        n = len(s)\n",
    "        dic = collections.defaultdict(lambda: collections.deque())\n",
    "        for i in range(n):\n",
    "            dic[int(s[i])].append(i)\n",
    "        for c in t:\n",
    "            if not dic[int(c)]:\n",
    "                return False\n",
    "            cur = dic[int(c)][0]\n",
    "            for val in range(int(c)):\n",
    "                if dic[val] and dic[val][0] < cur:\n",
    "                    return False \n",
    "            dic[int(c)].popleft()\n",
    "        return True\n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        C1 = Counter(s);C2 = Counter(t)\n",
    "        for i in C1.keys():\n",
    "            if C1[i] != C2[i]:return False\n",
    "        n = len(s)\n",
    "        G = {i:[] for i in range(10)}\n",
    "        for idx,i in enumerate(s):\n",
    "            I = int(i)\n",
    "            heappush(G[I],idx)\n",
    "        \n",
    "        for i in t:\n",
    "            I = int(i)\n",
    "            if any(G[j] and G[j][0] < G[I][0] for j in range(I)):\n",
    "                return False\n",
    "            heappop(G[I])\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        from collections import defaultdict\n",
    "        # stack用于储存元素在s中出现的位置\n",
    "        stack = defaultdict(list)\n",
    "        for i in range(len(s)):\n",
    "            stack[int(s[i])].append(i)\n",
    "        \n",
    "        # 逆序遍历t字符串,若不存在该字符,或存在比当前元素更大的元素在该元素的后面,则无法排序得到\n",
    "        for i in range(len(t) - 1,-1,-1):\n",
    "            v = t[i]\n",
    "            if stack[int(v)] == []:\n",
    "                return False\n",
    "            for j in range(int(v) + 1,10):\n",
    "                if stack[j] and stack[int(v)][-1] < stack[j][-1]:\n",
    "                    return False\n",
    "            # 弹出当前元素的最后一个索引\n",
    "            stack[int(v)].pop()\n",
    "        \n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        s_list = [0]*10\n",
    "        t_list = [0]*10\n",
    "        for i in s:\n",
    "            s_list[int(i)] += 1\n",
    "        for i in t:\n",
    "            t_list[int(i)] += 1\n",
    "        if s_list != t_list:\n",
    "            return False\n",
    "        \n",
    "        pos_list = [[] for i in range(10)]\n",
    "        for i in range(len(s)):\n",
    "            pos_list[int(s[i])].append(i)\n",
    "        \n",
    "        for ti in t:\n",
    "            digit = int(ti)\n",
    "            for j in range(digit):\n",
    "                if pos_list[j] and pos_list[j][0] < pos_list[digit][0]:\n",
    "                    return False\n",
    "            pos_list[digit].pop(0)\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        from collections import defaultdict\n",
    "        # stack用于储存元素在s中出现的位置\n",
    "        stack = defaultdict(list)\n",
    "        for i in range(len(s)):\n",
    "            stack[int(s[i])].append(i)\n",
    "        \n",
    "        # 逆序遍历t字符串,若不存在该字符,或存在比当前元素更大的元素在该元素的后面,则无法排序得到\n",
    "        for i in range(len(t) - 1,-1,-1):\n",
    "            v = t[i]\n",
    "            if stack[int(v)] == []:\n",
    "                return False\n",
    "            for j in range(int(v) + 1,10):\n",
    "                if stack[j] and stack[int(v)][-1] < stack[j][-1]:\n",
    "                    return False\n",
    "            # 弹出当前元素的最后一个索引\n",
    "            stack[int(v)].pop()\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        # 可以将任意区间的排序，拆分成若干次的长度为2子串的冒泡排序\n",
    "        n = len(s)\n",
    "        rec = [list() for _ in range(10)]\n",
    "        for i,c in enumerate(s):\n",
    "            rec[ord(c)-ord('0')].append(i)\n",
    "        \n",
    "        # 对于t的每一个字符，对应s里的第一个与之相同的字符\n",
    "        # 则必须满足：s里的这个字符之前的所有字符，都比这个字符大。\n",
    "        # 即比它小的字符，都在它右边\n",
    "        for i,c in enumerate(t):\n",
    "            cur_idx = ord(c)-ord('0')\n",
    "            if len(rec[cur_idx])==0:\n",
    "                return False\n",
    "            first = rec[cur_idx][0]\n",
    "            rec[cur_idx].pop(0)\n",
    "            for j in range(0,cur_idx):\n",
    "                if len(rec[j])>0 and rec[j][0]<first:\n",
    "                    return False\n",
    "                \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        if sorted(s) != sorted(t):  # 快速检查是否存在不匹配的字符\n",
    "            return False\n",
    "        \n",
    "        # 为s和t中的每个字符建立一个索引队列\n",
    "        idx_queues = {i: deque() for i in range(10)}\n",
    "        for i, char in enumerate(s):\n",
    "            idx_queues[int(char)].append(i)\n",
    "        \n",
    "        for char in t:\n",
    "            digit = int(char)\n",
    "            if not idx_queues[digit]:  # 如果需要的字符不存在，则返回False\n",
    "                return False\n",
    "            # 检查较小的字符是否在当前字符的前面\n",
    "            for i in range(digit):\n",
    "                if idx_queues[i] and idx_queues[i][0] < idx_queues[digit][0]:\n",
    "                    return False\n",
    "            idx_queues[digit].popleft()  # 删除已处理的字符索引\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        # 可以将任意区间的排序，拆分成若干次的长度为2子串的冒泡排序\n",
    "        rec = [list() for _ in range(10)]\n",
    "        for i,c in enumerate(s):\n",
    "            rec[ord(c)-ord('0')].append(i)\n",
    "        \n",
    "        # 对于t的每一个字符，对应s里的第一个与之相同的字符\n",
    "        # 则必须满足：s里的这个字符之前的所有字符，都比这个字符大。\n",
    "        # 即比它小的字符，都在它右边\n",
    "        for i,c in enumerate(t):\n",
    "            cur_idx = ord(c)-ord('0')\n",
    "            if len(rec[cur_idx])==0:\n",
    "                return False\n",
    "            first = rec[cur_idx][0]\n",
    "            rec[cur_idx].pop(0)\n",
    "            for j in range(0,cur_idx):\n",
    "                if len(rec[j])>0 and rec[j][0]<first:\n",
    "                    return False\n",
    "                \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        l = []\n",
    "        for i in range(10): l.append([])\n",
    "        for idx, num in enumerate(s):\n",
    "            l[int(num)].append(idx)\n",
    "\n",
    "        for num_str in t:\n",
    "            num = int(num_str)\n",
    "            if not l[num]: return False\n",
    "            num_idx = l[num][0]\n",
    "            for i in range(num):\n",
    "                if l[i] and l[i][0] < num_idx: return False\n",
    "            l[num].pop(0)\n",
    "\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        n = len(s)\n",
    "\n",
    "        dct = defaultdict(list)\n",
    "        for i in range(n):\n",
    "            dct[int(s[i])].append(i)\n",
    "        ind = defaultdict(int)\n",
    "\n",
    "        for i in range(n):\n",
    "            d = int(t[i])\n",
    "            if ind[d] >= len(dct[d]):\n",
    "                return False\n",
    "\n",
    "            for j in range(d):\n",
    "                if ind[j] < len(dct[j]) and dct[j][ind[j]] < dct[d][ind[d]]:\n",
    "                    return False\n",
    "            ind[d] += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str | List[str], t: str) -> bool:\n",
    "        if Counter(s) != Counter(t):\n",
    "            return False\n",
    "        s = list(s)\n",
    "        mp = defaultdict(deque)\n",
    "        for i, ch in enumerate(s):\n",
    "            mp[ch].append(i)\n",
    "        for ch in t:\n",
    "            v = mp[ch]\n",
    "            if len(v) == 0:\n",
    "                return False\n",
    "            for less in range(int(ch)):\n",
    "                less = str(less)\n",
    "                if len(mp[less]) > 0 and mp[less][0] < v[0]:\n",
    "                    return False\n",
    "            mp[ch].popleft()\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        mp = defaultdict(deque)\n",
    "        # mp = {j}\n",
    "        for i, digit in enumerate(s):\n",
    "            mp[int(digit)].append(i)\n",
    "        print(f'{mp}')\n",
    "        for i, digit in enumerate(t):\n",
    "            d = int(digit)\n",
    "            if not len(mp[d]):\n",
    "                return False\n",
    "            for j in range(d):\n",
    "                # if mp[j]:\n",
    "                #     print(f'mp = {mp[j]}, i = {i}')\n",
    "                if mp[j] and mp[j][0] < mp[d][0]:\n",
    "                    # print(f'mp={mp[j]}')\n",
    "                    return False\n",
    "            mp[d].popleft() \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isTransformable(self, s: str, t: str) -> bool:\n",
    "        if Counter(s) != Counter(t):\n",
    "            return False\n",
    "        \n",
    "        c = [0] * 10\n",
    "        d = [deque() for _ in range(10)]\n",
    "        for i in map(int, s):\n",
    "            d[i].append(c[:i])\n",
    "            c[i] += 1\n",
    "\n",
    "        c = [0] * 10\n",
    "        for i in map(int, t):\n",
    "            x = d[i].popleft()\n",
    "            if any(a > b for a,b in zip(x, c[:i])):\n",
    "                return False\n",
    "            c[i] += 1\n",
    "        return True\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
